Conventionally, the Viterbi decoding technique for performing maximum likelihood decoding of convolutional codes has been known. In this Viterbi decoding technique, since a sequence closest to the received code sequence is selected, based on the Viterbi decoding algorithm, from the code sequences which could be generated on the transmitting side encoder, it is possible to decode the received codes even when they involve errors. In this way, the Viterbi decoding technique has a high correcting capability against random errors arising over the communication path, and in particular, this technique can provide a great coding gain when combined with soft decision decoding. Therefore, Viterbi decoders have been widely adopted to decode error correction codes for mobile communications systems and others.
To begin with, the Viterbi algorithm will be described briefly with reference to convolutional codes with a coding rate of 1/2 and a constraint length K=3 which are given by generator polynomials,G1(D)=1+D2 G2(D)=1+D+D2                 where ‘D’ indicates the data delay and ‘+’ indicates addition of one bit only.        
FIG. 1 is a block diagram showing a configuration of a Viterbi decoder for generating the above convolutional codes. As shown in FIG. 1, the Viterbi decoder is comprised of shift registers, namely registers 101A and 101B, and adders 102A, 102B and 102C for performing modulo-two addition. This decoder has four internal states, each given by (b1, b2), explicitly: internal state (0,0), internal state (0,1), internal state (1,0) and internal state (1,1). Each internal state can make a transition to two internal states when an input is given.
Specifically, as shown in FIG. 2, in the case of internal state (0,0) the decoder makes a transition to internal state (0,0) when the input is 0 and a transition to internal state (0,1) when the input is 1; in the case of internal state (0,1) the decoder makes a transition to internal state (1,0) when the input is 0 and a transition to internal state (1,1) when the input is 1; in the case of the internal state (1,0) the decoder makes a transition to internal state (0,0) when the input is 0 and a transition to internal state (0,1) when the input is 1; and in the case of the internal state (1,1) the decoder makes a transition to internal state (1,0) when the input is 0 and a transition to internal state (1,1) when the input is 1.
FIG. 3 is a trellis diagram showing the above internal state transitions. In the diagram, the branches represented by solid line indicate transitions when the input is ‘0’ and the branches represented by dashed line indicate transitions when the input is ‘1’. The numerals attached to each branch are the code symbols (G1, G2) output when the transition of the branch occurs. As seen in this diagram, two paths always merge at each state. In the Viterbi algorithm, the maximum likelihood path is selected from the two paths at each internal state, and when survivor paths up to a predetermined length have been selected, the most probable one is detected from the selected paths at different internal states to thereby decode the received codes.
The selection of the maximum likelihood path is made based on the probability information of each of the merging paths. In a hard-decision Viterbi algorithm, the Hamming distances between each path bit sequence and the received bit sequence are summed to produce the probability of the path. In a soft-decision Viterbi algorithm, the squares of the Euclidean distances between each path bit sequence and the received bit sequence are summed to produce the probability of the path.
In the description hereinbelow, the value presenting the probability of a path is called path metric, and the value presenting the probability for each unit period of reception is called branch metric. The path metric can be translated as a sum of the probabilities of transitions to a certain internal state. The branch metric can be translated as a sum of the probabilities of individual bits at a transition from one internal state to the next internal state.
The Euclidean distance between two strings of data, i.e., received data (r1, r2) and data (s1, s2) generated by a transmission meter is given as expression as follows:√{square root over ((s1−r1)2+(s2−r2)2)}{square root over ((s1−r1)2+(s2−r2)2)}In Viterbi decoding, the square of the Euclidean distance is expressed as:(s1−r1)2+(s2−r2)2=s12−2×s1×r1+r12+s22−2×s2×r2+r22 and data (s1, s2) which minimizes the above value of the expression is determined.
Here, since received data (r1, r2) is fixed and hence r1 and r2 are constant regardless of the values (s1, s2), these can be omitted from the expression. Further, as to the transmitted data (s1, s2), for elements s1 and s2, assuming s1 or s2 to be ‘−1’ when the data is ‘0’ and assuming s1 or s2 to be ‘1’ when the data is ‘1’, s12 and s22 are constant regardless of the values (s1, s2), so that these can be omitted from the expression. Further, when the remaining part is divided by 2, the expression is reduced to −s1×r1−s2×r2.
From this expression, if s1=−1, −s1×r1 is r1. Hence if r1=−1, the term −s1×r1 is reduced to −1, if r1=0, the term is reduced to 0, and if r1=1, the term is reduced to 1. If s1=1, −s1×r1 is −r1. Hence if r1=−1, the term is reduced to 1, if r1=0, the term is reduced to 0, and if r1=−1, the term is reduced to 1.
Accordingly, −s1×r1 results in a value linearly varying from 0 to 2 in accordance with received data r1(−1 to 1) if s1=−1 whereas −s1×r1 results in a value linearly varying from 2 to 0 in accordance with received data r1 (−1 to 1) if s1=1. When the resolution of received data r1 shown in FIG. 4 is set at 3 bits, the metrics shown in FIG. 5 can be obtained from the above method.
Next, operations based on soft-decision processing will be described. In contrast to the hard-decision process which uses binary signals ‘0’ and ‘1’, the soft-decision process performs decisions based on multi-levels signals. In soft-decision using eight levels with three bits as shown in FIGS. 4 and 5, assuming only one bit data, when the information bit is ‘0’, if the received level is ‘0’, the branch metric results in ‘0’ and if the received level is ‘7’, the branch metric results in ‘7’. When the information bit is ‘1’, if the received level is ‘01’, the branch metric results in ‘7’ and if the received level is ‘7’, the branch metric results in ‘0’. It should be noted that the smaller this branch metric value, the more probable the branch is.
FIG. 6 is a trellis diagram showing a soft-decision metric processing example. In this soft-decision metric process, suppose that an information sequence is given as ‘0110000’, the code sequence is given as ‘00’, ‘11’, ‘10’, ‘10’, ‘11’, ‘00’ and ‘00’, and the received sequence is given as ‘2’, ‘4’, ‘3’, ‘6’, ‘7’, ‘2’, ‘7’, ‘5’, ‘5’, ‘7’, ‘1’, ‘0’, ‘1’ and ‘2’. For the transition from the internal state ‘00’ at time instant ‘0’ to the internal state ‘00’ at time instant ‘1’, since the probability for the first bit ‘0’ is ‘2’ and the probability for the second bit ‘0’ is ‘4’, the metric results in ‘2+4’=‘6’. The branch metrics for all the paths can be obtained in the same way. In the diagram, the numeral along each line segment denotes the branch metric and the numeral in hatching located at each internal-state and time-instant point denotes the path metric.
As a result of the calculation, the two paths merging into the internal state ‘00’ at time instant ‘7’ are one from the internal state ‘00’ at time instant ‘6’ and the other from the internal state ‘10’ at time instant ‘6’. As to the path from the internal state ‘00’ at time instant ‘6’, the path metric at time instant ‘6’/internal state ‘00’ is ‘21’ and the branch metric from the internal state ‘00’ at time instant ‘6’ to the internal state ‘00’ at time instant ‘7’ is ‘3’, so that the probability of the path results in ‘24’. On the other hand, as to the path from the internal state ‘10’ at time instant ‘6’, the path metric at time instant ‘6’/internal state ‘10’ is ‘32’ and the branch metric from the internal state ‘10’ at time instant ‘6’ to the internal state ‘00’ at time instant ‘7’ is ‘11’, so that the probability of the path results in ‘43’. Therefore, ‘24’ is assumed as the path metric at time instant ‘7’/internal state ‘00’ that is, the path from the internal state ‘00’ at time instant ‘6’ to the internal state ‘00’ at time instant ‘7’ is selected. Here, in the diagram, ‘x’ denotes the discarded path at the merging point.
As shown in FIG. 7, by tracing the survivor path along the arrows or in the reverse direction of the sequence of the received data, the decoded result can be obtained. In FIG. 6, the underlined numerals of the received sequence denotes error bits in transmission. As understood from the decoded result, the original information sequence can be obtained even when three bits of errors have occurred.
FIG. 8 shows a typical configuration of a Viterbi decoder for decoding convolutional codes based on the Viterbi algorithm, which is comprised of a branch metric calculator 1 for calculating the branch metric between the received sequence and each branch; an ACS portion 2 for selecting the survivor path and calculating the path metric of the survivor path; a path metric memory 3 for storing the path metric value at each internal state; a path memory 4 for storing the estimated output of a selected path; and a backtracing processor 5 for detecting the address of the most probable path metric and performing control of the path memory.
The Viterbi decoder thus configured operates, as shown in the flowchart in FIG. 9, in such a manner that it reads the received data and calculates branch metrics and updates the path metric into the path memory (Steps S2 to S5) until one entire frame is completed and when the frame has been completed (Step S1) then it outputs the decoded result by backtracing (Step S6).
For such Viterbi decoders, various techniques have been proposed in order to improve calculation efficiency. As shown in FIG. 10, a technique (see Japanese Patent Application Laid-Open Sho 63 No. 122323) is disclosed in which a soft-decision data converting circuit A is provided so as to convert the input data in accordance with the circumstances so that it is used for calculations of branch metrics to thereby assign weights to the input bits. Another technique (see Japanese Patent Application Laid-Open Hei 7 No. 245567) is disclosed as shown in FIG. 11, in which a normalizing circuit (maximum likelihood value subtraction) B is provided to search for the maximum likelihood value from all the branch metrics and subtract the value from each branch metric so as to narrow the data range to thereby determine the maximum likelihood value in branch metric.
Use of soft-decision of the Viterbi algorithm improves error collection characteristics as the bit precision of input data is enhanced, as seen in the BER characteristic chart in FIG. 12. However, enhancement of the bit precision of input data increases the number of bits handled in the internal processor, leading to the problem of system scale enlargement. The same problem occurs with the method of assigning weights on the input bits and with the normalizing method by determining the maximum likelihood value in branch metric.
Illustratively, as shown in the BER characteristic chart in FIG. 12, in a case of a Viterbi decoding process with a constraint length of 9 and a coding rate of 1/3, for example, when the bit accuracy of input data is set at three bits, the data can be correctly processed by an ACS portion having six or more internal operational bits if the process is combined with appropriate normalization. However, when the input bit accuracy is set at four bits, not less than 7 or 8 internal operational bits are needed in the ACS portion even in combination with an appropriate normalization process. The internal operational bit length increases from six bits to 8 bits, the circuit scale also needs to be enlarged proportionally, to as large as a little over 1.3 times.
It is therefore an object of the present invention to provide a Viterbi decoder which is able to improve error correction characteristics while suppressing enlargement of the system scale.